package com.xw.class09;

import java.util.HashMap;

/**
 * @author: xw
 * @create: 2023/6/5 16:55
 * @description:一个单链表有next指针，有random指针，random可能指向自己，指向空，也可能多个指向一个
 */
public class Code04_CopyListWithRandom {

    static class Node {
        public int value;
        public Node next;
        public Node random;

        public Node(int value){
            this.value = value;
        }
    }

    /**
     * 复制复杂链表
     * @param head
     * @return
     */
    public static Node copyRandomList1(Node head){
        if (head == null) {
            return head;
        }
        HashMap<Node, Node> flag = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            flag.put(cur,new Node(cur.value));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            flag.get(cur).next = flag.get(cur.next);
            flag.get(cur).random = flag.get(cur.random);
        }
        return flag.get(head);
    }

    public  static Node copyRandomList2(Node head){
        if (head == null) {
            return head;
        }
        Node cur = head;
        Node next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        Node copy = null;
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            copy.random = cur.random != null ? cur.random.next : null;
            cur = next;
        }
        //把链表的顺序调整正确
        Node res = head.next;
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            cur.next = next;
            copy.next = next != null ? next.next : null;
            cur = next;
        }
        return res;
    }
}
